package com.topcoder.tccr411;

import java.util.Comparator;
import java.util.PriorityQueue;

public class BombMan {
	private int 					M;
	private int 					N;
	private boolean[][] 			wall;
	private int[][][]				times;
	private PriorityQueue<State>	pq;
	
	public int shortestPath(String[] maze, int bombs) {
		M = maze.length;
		N = maze[0].length();
		wall = new boolean[M][N];
		times = new int[M][N][101];
		
		Point start=null, end=null;
		for (int i=0; i<M; i++) {
			for (int j=0; j<N; j++) {
				for (int k=0; k<=100; k++) times[i][j][k] = Integer.MAX_VALUE;
				
				switch (maze[i].charAt(j)) {
				case '#':
					wall[i][j] = true;
					break;
				case 'B':
					start = new Point(i, j);
					break;
				case 'E':
					end = new Point(i, j);
				}
			}
		}
		
		pq = new PriorityQueue<State>(10, new Comparator<State>(){
			public int compare(State a, State b) {
				return a.time - b.time;
			}
		});
		pq.add(new State(start.x, start.y, 0, bombs));
		
		while (!pq.isEmpty()) {
			State s = pq.remove();
			if (s.x==end.x && s.y==end.y) return s.time;
			if (times[s.x][s.y][s.bombs] >= s.time) {
				times[s.x][s.y][s.bombs] = s.time;
				visit(s.x - 1, s.y, s.time, s.bombs);
				visit(s.x + 1, s.y, s.time, s.bombs);
				visit(s.x, s.y - 1, s.time, s.bombs);
				visit(s.x, s.y + 1, s.time, s.bombs);
			}
		}
		
		return -1;
	}
	
	private void visit(int x, int y, int time, int bombs) {
		if (x<0 || x>=M || y<0 || y>=N) return;
		if (wall[x][y]) {
			if (bombs == 0) return;
			time += 3;
			bombs--;
		}
		else {
			time++;
		}
		if (times[x][y][bombs] > time) {
			pq.add(new State(x, y, time, bombs));
			times[x][y][bombs] = time;
		}
	}
	
	private class State {
		int x, y;
		int time;
		int bombs;
		public State(int x, int y, int time, int bombs) {
			this.x = x;
			this.y = y;
			this.time = time;
			this.bombs = bombs;
		}
	}
	
	private class Point {
		int x, y;
		public Point(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}
}
